package cn.handong.tool.algorithm.图;

import cn.handong.tool.algorithm.model.TreeNode;

import java.util.*;

public class GasStation {
    /**
     * 首先判断总gas能不能大于等于总cost，如果总gas不够，一切都白搭对吧（总（gas- cost）不用单独去计算，
     * 和找最低点时一起计算即可，只遍历一次）；
     * <p>
     * 再就是找总（gas-cost）的最低点，不管正负（当然如果最低点都是正的话那肯定能跑完了）；
     * <p>
     * 找到最低点后，如果有解，那么解就是最低点的下一个点，因为总（gas-cost）是大于等于0的，
     * 所以前面损失的gas我从最低点下一个点开始都会拿回来！
     * 别管后面的趋势是先加后减还是先减后加，最终结果我是能填平前面的坑的。
     */
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int len = gas.length;
        int spare = 0;
        int minSpare = Integer.MAX_VALUE;
        int minIndex = 0;
        for (int i = 0; i < len; i++) {
            spare += gas[i] - cost[i];
            if (spare < minSpare) {
                minSpare = spare;
                minIndex = i;
            }
        }
        return spare < 0 ? -1 : (minIndex + 1) % len;
    }


    // 暴力破解
    public int canCompleteCircuit1(int[] gas, int[] cost) {
        int n = gas.length;
        for (int i = 0; i < n; i++) {
            int j = i;
            int remain = gas[i];
            while (remain - cost[i] >= 0) {
                remain = remain - cost[i] + gas[(j + 1) % n];
                j = (j + 1) % n;
                if (j == i) {
                    return i;
                }
            }
        }
        return -1;
    }


    // 优化
    public int canCompleteCircuit2(int[] gas, int[] cost) {
        int n = gas.length;
        int[] farIndex = new int[n];
        for (int i = 0; i < n; i++) {
            farIndex[i] = -1;
        }
        int[] farIndexRemain = new int[n];
        for (int i = 0; i < n; i++) {
            int j = i;
            int remain = gas[i];
            while (remain - cost[j] >= 0) {
                remain = remain - cost[j];
                j = (j + 1) % n;
                if (farIndex[j] != -1) {
                    remain = remain + farIndexRemain[j];
                    j = farIndex[j];
                } else {
                    remain = remain + gas[j];
                }
                if (j == i) {
                    return i;
                }
            }
            farIndex[i] = j;
            farIndexRemain[i] = remain;
        }
        return -1;
    }


    // 优化2
    public int canCompleteCircuit3(int[] gas, int[] cost) {
        int n = gas.length;
        for (int i = 0; i < n; i++) {
            int j = i;
            int remain = gas[i];
            while (remain - cost[j] >= 0) {
                remain = remain - cost[j] + gas[(j + 1) % n];
                j = (j + 1) % n;
                if (j == i) {
                    return i;
                }
            }
            if (j < i) {
                return -1;
            }
            i = j;
        }
        return -1;
    }


    public boolean lemonadeChange(int[] bills) {
        int five = 0, ten = 0;
        for (int bill : bills) {
            if (bill == 5) {
                five++;
            } else if (bill == 10) {
                if (five == 0) {
                    return false;
                }
                ten++;
                five--;
            } else {
                if (five > 0 && ten > 0) {
                    five--;
                    ten--;
                } else if (five >= 3) {
                    five -= 3;
                } else {
                    return false;
                }
            }
        }
        return true;
    }


    public boolean checkPossibility(int[] nums) {
        int n = nums.length;
        for (int i = 0; i < n - 1; i++) {
            int x = nums[i], y = nums[i + 1];
            if (x > y){
                nums[i] = y;
                if (isSorted(nums)){
                    return true;
                }
                nums[i] = x;
                nums[i + 1] = x;
                return isSorted(nums);
            }
        }
        return true;
    }


    public boolean isSorted(int[] nums) {
        int n = nums.length;
        for (int i = 1; i < n; i++) {
            if (nums[i - 1] > nums[i]){
                return false;
            }
        }
        return true;
    }




    public boolean checkPossibility1(int[] nums) {
        int n = nums.length, cnt = 0;
        for (int i = 0; i < n-1; i++) {
            int x = nums[i], y = nums[i+1];
            if (x > y){
                cnt++;
                if (cnt >= 2){
                    return false;
                }
                if (i > 0 && y < nums[i - 1]){
                    nums[i + 1] = x;
                }
            }
        }
        return true;
    }






    public List<List<Integer>> threeSum(int[] nums) {
        int n = nums.length;
        Arrays.sort(nums);
        List<List<Integer>> ans = new ArrayList<>();
        for (int k = 0; k < n - 2; k++) {
            if (nums[k] > 0) break;
            if (k > 0 && nums[k] == nums[k - 1]) continue;
            int i = k + 1, j = n - 1;
            while (i < j){
                int sum = nums[k] + nums[i] + nums[j];
                if (sum < 0){
                    while(i < j && nums[i] == nums[++i]);
                }else if (sum > 0){
                    while(i < j && nums[j] == nums[--j]);
                }else {
                    ArrayList<Integer> list = new ArrayList<>(Arrays.asList(nums[k], nums[i], nums[j]));
                    if (!ans.contains(list)){
                        ans.add(list);
                    }
                    while(i < j && nums[i] == nums[++i]);
                    while(i < j && nums[j] == nums[--j]);
                }
            }
        }
        return ans;
    }




    public List<List<Integer>> levelOrder(TreeNode node){
        if (node == null){
            return null;
        }
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> temp;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(node);
        while (!queue.isEmpty()){
            temp = new ArrayList<>();
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode remove = queue.remove();
                if (remove.left != null){
                    queue.add(remove.left);
                }
                if (remove.right != null){
                    queue.add(remove.right);
                }
                temp.add(remove.val);
            }
            res.add(temp);
        }
        return res;
    }

    public int maxDepth(TreeNode root){
        return root == null ? 0 : Math.max(maxDepth(root.left),maxDepth(root.right))+1;
    }


    private static int[] mergeSort(int[] nums) {
        if (nums.length <= 1){
            return nums;
        }
        int len = nums.length;
        int mid = len / 2;
        return merge(mergeSort(Arrays.copyOfRange(nums,0,mid)),mergeSort(Arrays.copyOfRange(nums,mid,len)));
    }

    public static int[] merge(int[] left,int[] right){
        int[] res = new int[left.length + right.length];
        int i = 0, j = 0;
        for (int index = 0; index < res.length; index++) {
            if (i >= left.length){
                res[index] = right[j++];
            }else if (j >= right.length){
                res[index] = left[i++];
            }else if (left[i] >= right[j]){
                res[index] = right[j++];
            }else {
                res[index] = left[i++];
            }
        }
        return res;
    }

}


















